/*
 * binaryheap.h
 *
 * 一个简单的二叉堆实现
 *
 * Portions Copyright (c) 2012-2022, PostgreSQL Global Development Group
 *
 * src/include/lib/binaryheap.h
 */

#ifndef BINARYHEAP_H
#define BINARYHEAP_H

/*
 * 对于最大堆，比较器必须返回 <0 当且仅当 a < b，返回 0 当且仅当 a == b，
 * 和 >0 当且仅当 a > b。对于最小堆，条件是反转的。
 */
typedef int (*binaryheap_comparator) (Datum a, Datum b, void *arg);

/*
 * binaryheap
 *
 *		bh_size			当前在 "nodes" 中的节点数量
 *		bh_space		"nodes" 中可以存储的节点数量
 *		bh_has_heap_property	自上次堆构建以来没有无序操作
 *		bh_compare		定义堆性质的比较函数
 *		bh_arg			用作比较函数的用户数据
 *		bh_nodes		可变长度的 "space" 节点数组
 */
typedef struct binaryheap
{
	int			bh_size;
	int			bh_space;
	bool		bh_has_heap_property;	/* 调试交叉检查 */
	binaryheap_comparator bh_compare;
	void	   *bh_arg;
	Datum		bh_nodes[FLEXIBLE_ARRAY_MEMBER];
} binaryheap;

extern binaryheap *binaryheap_allocate(int capacity,
									   binaryheap_comparator compare,
									   void *arg);
extern void binaryheap_reset(binaryheap *heap);
extern void binaryheap_free(binaryheap *heap);
extern void binaryheap_add_unordered(binaryheap *heap, Datum d);
extern void binaryheap_build(binaryheap *heap);
extern void binaryheap_add(binaryheap *heap, Datum d);
extern Datum binaryheap_first(binaryheap *heap);
extern Datum binaryheap_remove_first(binaryheap *heap);
extern void binaryheap_replace_first(binaryheap *heap, Datum d);

#define binaryheap_empty(h)			((h)->bh_size == 0)

#endif							/* BINARYHEAP_H */
